def GetNext(p):
	pLen = len(p)
	next = [0]*pLen
	next[0] = -1
	k = -1
	j = 0
	while(j < pLen-1):
		if(k == -1 or p[j] == p[k]):
			k += 1
			j += 1
			if(p[j] != p[k]):
				next[j] = k
			else:
				next[j] = next[k]
		else:
			k = next[k]
	return next

def KmpSearch(s, p):
	i = 0
	j = 0
	sLen = len(s)
	pLen = len(p)
	next = GetNext(p)
	while(i < sLen and j < pLen):
		if(j == -1 or s[i] == p[j]):
			i += 1
			j += 1
		else:
			j = next[j]
	if(j == pLen):
		return i - j
	else:
		return -1
		
KmpSearch("BBC ABCDAB ABCDABCDABDE", "ABCDABD")